﻿///////////////////////大数加法：
//以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。
//数据范围：
//100000
//s.length, t.length≤100000，字符串仅由'0'~‘9’构成
//要求：时间复杂度
//�
//(
//    �
//)
//O(n)
//示例1
//输入：
//"1", "99"
//复制
//返回值：
//"100"
//复制
//说明：
//1 + 99 = 100
//示例2
//输入：
//"114514", ""
//复制
//返回值：
//"114514"




//思路：栈+分步加法，这里由于可能一开始思路是直接转成整型或者longlong然后再相加，然而试过就知道了这种方法直接否掉了，因此我们可以借助一个栈的方法得到它的尾位然后依次保留商，依次与余数叠加放入新的栈，最后来个调整即可得到正确字符串，这里特别细的细节也没用，按着这样的思路就好。

 //1.s与t分别遍历后放入两个栈里。
  //2·分别取完栈顶元素后再pop然后完成一系列叠加操作，取余放入新栈。
  //3·把新栈中的元素遍历出string中返回即可。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        stack<char> s1, s2, ret;
        char top1 = '0', top2 = '0';
        int discuss = 0;
        for (int i = 0; i < s.size(); i++) s1.push(s[i]);
        for (int i = 0; i < t.size(); i++) s2.push(t[i]);
        while (!s1.empty() || !s2.empty() || discuss) {
            if (!s1.empty())  top1 = s1.top(); //这里不能pop，赋完值后pop

            if (!s2.empty())top2 = s2.top(); //这里不能pop，赋完值后pop



            int val1 = s1.empty() ? 0 : top1 - '0';
            int val2 = s2.empty() ? 0 : top2 - '0';
            if (!s1.empty()) s1.pop();
            if (!s2.empty()) s2.pop();


            int sum = val1 + val2 + discuss;
            discuss = sum / 10;
            ret.push(sum % 10 + '0');

        }
        string ans;
        while (!ret.empty()) {
            ans += ret.top();
            ret.pop();
        }
        return ans;

    }
};